package 我的Java学习_算法基础.day_03;

import java.util.Arrays;

public class _049_计数排序 {
    public static void main(String[] args) {
//        int[] a = {5, 3, 6, 2, 99,9,28};
        int[] a = {-3,-24,-2,4,-3};
//        int[] a = {-3, -24, -2, -4, -3};
        countSort(a);
        System.out.println(Arrays.toString(a));
    }

    /**
     * 计数排序
     * 时间复杂度：N+N+K(原始数组中最大值)
     * 空间复杂度：原数组中最大元素值（负数取绝对值）
     * 非原址排序
     * 稳定性：相同元素不会出现交叉，非原址都是拷来拷去
     * 如果要优化，辅助数组长度为max-min+1，可以缩短一点数组长度
     * 计数有缺陷，数组较为稠密，范围较小时适用
     * @param source 要排序的数组
     */
    public static void countSort(int[] source) {
        int maxPositive = source[0], minNegative = source[0];
        int flagNegative = 0;      //为1，则有负数
        int flagPositive = 0;      //为1，则有正数
        for (int i : source        //求数组元素绝对最大值
        ) {
            if (i < 0) {
                flagNegative = 1;
                if (i < minNegative) {
                    minNegative = i;
                }
            } else {
                flagPositive = 1;
                if (i > maxPositive) {
                    maxPositive = i;
                }
            }
        }
        int current = 0;        //指针，用于将辅助数组的数填到原始数组
        if (flagNegative != 1) {  //数组元素只存在存在正数
            int[] positiveHelper = new int[maxPositive + 1];
            for (int i : source     //将原数组值作为辅助数组下标，将该位加1
            ) {
                positiveHelper[i]++;
            }
            for (int i = 0; i < positiveHelper.length; i++) {
                while (positiveHelper[i] > 0) { //将辅助数组元素非零下标，赋值给原数组
                    source[current++] = i;
                    positiveHelper[i]--;
                }
            }
        }
        if (flagPositive != 1) {   //数组元素只存在负数
            int[] negativeHelper = new int[Math.abs(minNegative) + 1];
            for (int i:source
                 ) {
                negativeHelper[Math.abs(i)]++;  //取绝对值做辅助数组下标
            }
            //元素小的取绝对值，反而大，逆序读取
            for (int i = negativeHelper.length - 1; i >= 0; i--) {
                while (negativeHelper[i] > 0) {
                    source[current++] = -i;
                    negativeHelper[i]--;
                }
            }

        }
        //前两种结合
        if ((flagPositive == 1) && (flagNegative == 1)) {  //数组元素有负有正
            int[] positiveHelper = new int[maxPositive + 1];
            int[] negativeHelper = new int[Math.abs(minNegative) + 1];
            for (int i : source
            ) {
                if (i > 0) {
                    positiveHelper[i]++;
                } else {
                    negativeHelper[Math.abs(i)]++;
                }
            }
            for (int i = negativeHelper.length - 1; i >= 0; i--) {
                while (negativeHelper[i] > 0) {
                    source[current++] = -i;
                    negativeHelper[i]--;
                }
            }
            for (int i = 0; i < positiveHelper.length; i++) {
                while (positiveHelper[i] > 0) {
                    source[current++] = i;
                    positiveHelper[i]--;
                }
            }
        }
    }
}
